各位大佬都用的 二分,蒟蒻介绍一种简单方法。
式很好列:
表示将 到 的贞鱼在同一车的怨气值 , 决策具有单调性。
不如将当前的决策点区间记为 $ [optl,optr] $ , 处理 的区间为 $ [L,R] $
我们可以暴力计算 的值 , 并记录当前的决策点。
然后我们可以递归计算 与
因为决策具有单调性 , 所以计算 时只需用 , 计算 时只需用。
这种方法仅适用于有决策单调性的题,时间复杂度为
#include <cstdio>
#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f
void Read( int &x ) {
x = 0; int f = 1;
char s = getchar( );
for( ; s < '0' || s > '9' ; s = getchar( ) ) f = s == '-' ? -f : f;
for( ; s >= '0' && s <= '9' ; s = getchar( ) ) x = x * 10 + s - '0';
x *= f;
}
void Write( int x ) {
if( x < 0 )
putchar('-') , x = -x;
if( x >= 10 ) Write( x / 10 );
putchar( x % 10 + '0' );
}
const int MAXK = 800 , MAXN = 4000;
int n , k , x , sum[ MAXN + 5 ][ MAXN + 5 ];
int dp[ MAXK + 5 ][ MAXN + 5 ];
int Calc( int u , int v ) {
return sum[ v ][ v ] - sum[ v ][ u - 1 ] - sum[ u - 1 ][ v ] + sum[ u - 1 ][ u - 1 ];
}
void dfs( int s , int L , int R , int optl , int optr ) {
if( L > R ) return;
int Mid = ( L + R ) / 2 , opt;
dp[ s ][ Mid ] = INF;
for( int i = optl ; i <= min( optr , Mid ) ; i ++ ) {
if( dp[ s ][ Mid ] > dp[ s - 1 ][ i - 1 ] + Calc( i , Mid ) ) {
dp[ s ][ Mid ] = dp[ s - 1 ][ i - 1 ] + Calc( i , Mid );
opt = i;
}
}
dfs( s , L , Mid - 1 , optl , opt );
dfs( s , Mid + 1 , R , opt , optr );
}
int main( ) {
Read( n ) , Read( k );
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= n ; j ++ )
Read( x ) , sum[ i ][ j ] = sum[ i - 1 ][ j ] + sum[ i ][ j - 1 ] - sum[ i - 1 ][ j - 1 ] + x;
for( int i = 1 ; i <= n ; i ++ )
dp[ 0 ][ i ] = INF;
for( int i = 1 ; i <= k ; i ++ )
dfs( i , 1 , n , 1 , n );
Write( dp[ k ][ n ] / 2 );
return 0;
}